// 给定一个未排序的整数数组nums和一个整数k，返回数组中第k个最大的元素
// 要求以时间复杂度为O(n)的算法解决

// 思路：排序后取数组第k位最大的数，冒泡，选择，插入排序的时间复杂度太高，可以考虑堆排序，归并排序，快速排序
// 归并排序必须只有最后排序完毕才能返回第k个大的数，而堆排序每次排序之后，就会确定一个元素的准确排名，快速排序也是这样

// 解法1： 利用堆排序
// 步骤： 1. 将无序序列构造成第一个大顶堆，使得n个元素的最大值处于序列的第1个位置
// 2. 交换第一个元素（最大值元素）和第n个元素的位置，将序列前n-1个元素的子序列调整成一个新的大顶堆，从而确定第二个最大值元素
// 3. 直到获取第k个最大值元素

// 复杂度分析
// 时间复杂度： O(n * logn)
// 空间复杂度：O(1)

function findKthLargest(nums, k) {
    // 调整为大顶堆
    function heapify(nums, index, end) {
        let left = 2 * index + 1
        let right = left + 1
        while (left <= end) {
            let max_index = index
            if (nums[left] > nums[max_index]) {
                max_index = left
            }
            if (right <= end && nums[right] > nums[max_index]) {
                max_index = right
            }
            if (index === max_index) {
                // 不用交换，说明交换结束
                break
            }
            [nums[index], nums[max_index]] = [nums[max_index], nums[index]]
            // 继续调整子树
            index = max_index
            left = 2 * index + 1
            right = left + 1
        }
    }

    function buildMaxHeap(nums) {
        let size = nums.length
        for (let i = Math.floor(size / 2); i >= 0; i--) {
            heapify(nums, i, size - 1)            
        }
    }
    buildMaxHeap(nums)
    let size = nums.length
    for (let i = 0; i < k - 1; i++) {
        [nums[0], nums[size - i - 1]] = [nums[size - i - 1], nums[0]] 
        heapify(nums, 0, size - i - 2)
    }
    return nums[0]
}

let arr = [3, 2, 1, 5, 6, 4]
let k = 2
console.log(findKthLargest(arr, k));

// 解法2，快速排序
// 思路： 快速排序在每次调整结束，都会确定一个元素的最终位置，且以该元素为界限，将数组分成了左右两个子数组，左子数组中的元素都比该元素小
// 右子数组中的元素都比该元素大
// 只要某次划分的元素恰好是第k个下标就找到了答案，并且我们只需要关注第k个最大元素所在区间的排序情况，与第k个最大元素无关的区间排序可以忽略

// 复杂度分析
// 时间复杂度： O(n * logn)
// 空间复杂度：O(1)

function findKthLargest2(nums, k) {
    return quickSort(nums,0, nums.length, k)
}

function quickSort(arr, low, high, k) {
    let size = arr.length
    if (low < high) {
        // 按照基准数的位置，将序列分为左右两个子序列
        let pi = randomPartition(arr, low, high)
        if (pi === size - k) {
            return arr[size - k]
        } else if (pi > size - k) {
            // 对左子序列进行递归快速排序
            quickSort(arr, low, pi - 1, k)
        } else {
            // 对右子序列进行递归快速排序
            quickSort(arr, pi + 1, high, k)
        }
    }
    return arr[size - k]
}

function randomPartition(arr, low, high) {
    // 随机选择一个基准数
    let i = Math.floor(Math.random() * (high - low)) + low;
    // 将基准数与最低位互换
    [arr[i], arr[low]] = [arr[low], arr[i]]
    // 以最低位为基准数，然后将序列中比基准数大的元素移动到基准数右侧
    // 比基准数小的移动到基准数左侧，最后将基准数放到正确的位置上
    return partition(arr, low, high)
}

function partition(arr, low, high) {
    let pivot = arr[low]
    let i = low + 1 // 从基准数1位开始开始遍历，保证位置i之前的元素都小于基准数
    for (let j = i; j < arr.length; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
        }        
    }
    [arr[i - 1], arr[low]] = [arr[low], arr[i - 1]]
    // 返回基准的位置
    return i - 1
}

let arr1 = [3, 2, 1, 5, 6, 4]
let k1 = 1
console.log(findKthLargest2(arr1, k1));
